/**
 * Cursor-based IO for reading rating and query set files in the usual Netflix
 * formats. These cursors are intended to allow for fairly low memory usage.
 */
#ifndef U1_IO_H_
#define U1_IO_H_

#include <cassert>
#include <climits>
#include <iostream>
#include "u1.h"

#define BAD_ID -1

/* Read file with either format:
 * movie_id:                    -- start of a movie "block"
 * user_id,rating[,...]
 * user_id,rating[,...]
 * ...
 * or format:
 * user_id:                     -- start of user "block"
 * movie_id,rating[,...]
 * movie_id,rating[,...]
 * ...
 *
 * Example:
 * for(ratings_cursor_t<float> ts(cin); ts; ++ts)
 *   cout<<ts.block_id()<<":"<<ts.id()<<":"<<ts.rating()<<endl;
 */
template<typename rating_t>
class ratings_cursor_t {
  std::istream &is;
  int _line;
  rating_t _rating;
  int _block_id;
  int _id;
public:
  ratings_cursor_t(std::istream &is) : is(is)
  {
    _line = 0;
    _block_id = BAD_ID;
    ++(*this);
  }

  ratings_cursor_t<rating_t> &operator++()
  {
    char t;
    std::string dummy;
    if (is>>_id>>t) {
      if (t == ':') {
        _block_id = _id;
        ++(*this);
      } else {
        assert(_block_id != BAD_ID); // file should start with block id
        assert(t == ',');
        if (!(is>>_rating)) {
          TRACE<<"missing rating after "<<line()<<" lines";
        }
        std::getline(is, dummy);
      }
    } else {
      _block_id = BAD_ID;
    }
    return (*this);
  }

  operator bool() const
  {
    return _block_id != BAD_ID;
  }

  int line() const { return _line; }
  rating_t rating() const { return _rating; }
  int block_id() const { return _block_id; }
  int id() const { return _id; }
};

/* See superclass. This is syntactic sugar for the first format.
 *
 * Example:
 * for(ratings_by_movie_cursor_t<float> ts(cin); ts; ++ts)
 *   cout<<ts.movie_id()<<":"<<ts.user_id()<<":"<<ts.rating()<<endl;
 */
template<typename rating_t>
class ratings_by_movie_cursor_t : public ratings_cursor_t<rating_t>
{
public:
  ratings_by_movie_cursor_t(std::istream &is) : ratings_cursor_t<rating_t>(is) 
  { }
  int movie_id() const { return this->block_id(); }
  int user_id() const { return this->id(); }
};

/* See superclass. This is syntactic sugar for the second format.
 *
 * Example:
 * for(ratings_by_user_cursor_t<float> ts(cin); ts; ++ts)
 *   cout<<ts.user_id()<<":"<<ts.movie_id()<<":"<<ts.rating()<<endl;
 */
template<typename rating_t>
class ratings_by_user_cursor_t : public ratings_cursor_t<rating_t>
{
public:
  ratings_by_user_cursor_t(std::istream &is) : ratings_cursor_t<rating_t>(is)
  { }
  int movie_id() const { return this->id(); }
  int user_id() const { return this->block_id(); }
};

/* Helper for ratings_block_cursor. Note that id can refer to a movie
 * id or a user id, depending on the context. */
template <typename rating_t>
struct id_rating_t {
  id_rating_t() : id(BAD_ID), rating(0)
  { }
  id_rating_t(int id, rating_t rating) : id(id), rating(rating)
  { }
  int id;
  rating_t rating;
};

/* Default id rating i/o.
 */
template <typename rating_t>
std::ostream& operator<<(std::ostream &os, const id_rating_t<rating_t> &x) {
  return os<<x.id<<" "<<x.rating;
}
template <typename rating_t>
std::istream& operator>>(std::istream &is, id_rating_t<rating_t> &x) {
  return is>>x.id>>x.rating;
}

/**
 * Compare id_rating_t's by id.
 */
template <typename rating_t>
struct F_id_rating_id_less {
  bool operator()(const id_rating_t<rating_t> &r, int id) const {
    return r.id < id;
  }
  bool operator()(int id, const id_rating_t<rating_t> &r) const {
    return id < r.id;
  }
  bool operator()(const id_rating_t<rating_t> &r0,
      const id_rating_t<rating_t> &r1) const {
    return r0.id < r1.id;
  }
};

/* Like ratings_cursor_t but returns ratings in blocks.
 *
 * Example:
 * for(ratings_by_user_block_cursor_t<float> ts(cin); ts; ++ts) {
 *   cout<<ts.user_id()<<":"<<endl;
 *   for(vector<id_rating_t<float> >::const_iterator it = ts.begin();
 *     it != ts.end(); ++it)
 *   {
 *     cout<<it->id<<","<<it->rating<<endl;
 *   }
 * }
 */
template<typename rating_t>
class ratings_block_cursor_t : public std::vector<id_rating_t<rating_t> > {
  ratings_cursor_t<rating_t> _c;
  int _block_id;
public:
  ratings_block_cursor_t(std::istream &is) : _c(is) {
    ++(*this);
  }

  ratings_block_cursor_t<rating_t> &operator++()
  {
    if (_c) {
      this->clear();
      _block_id = _c.block_id();
      do {
        push_back(id_rating_t<rating_t>(_c.id(), _c.rating()));
        ++_c;
      } while (_c && _block_id == _c.block_id());
    } else {
      this->clear();
      _block_id = BAD_ID;
    }

    return *(this);
  }

  operator bool() const {
    return _block_id != BAD_ID;
  }

  int line() const { return _c.line(); }
  int block_id() const { return _block_id; }
  int id(size_t j) const { return (*this)[j].id; }
  rating_t rating(size_t j) const { return (*this)[j].rating; }
};

/* See superclass. This is syntactic sugar for the first format.
 */
template<typename rating_t>
class ratings_by_movie_block_cursor_t : public ratings_block_cursor_t<rating_t>
{
public:
  ratings_by_movie_block_cursor_t(std::istream &is)
    : ratings_block_cursor_t<rating_t>(is)
  { }
  int movie_id() const { return this->block_id(); }
  int user_id(size_t j) const { return this->id(j); }
};

/* See superclass. This is syntactic sugar for the second format.
 */
template<typename rating_t>
class ratings_by_user_block_cursor_t : public ratings_block_cursor_t<rating_t>
{
public:
  ratings_by_user_block_cursor_t(std::istream &is)
    : ratings_block_cursor_t<rating_t>(is)
  { }
  int movie_id(size_t j) const { return this->id(j); }
  int user_id() const { return this->block_id(); }
};

/* Reads file in format like qualifying set:
 * movie_id:                    -- start of a movie "block"
 * user_id[...]
 * user_id[...]
 * ...
 * or format:
 * user_id:                     -- start of user "block"
 * movie_id[...]
 * movie_id[...]
 * ...
 */
class query_cursor_t {
  std::istream &is;
  int _line;
  int _block_id;
  int _id;
public:
  query_cursor_t(std::istream &is);

  query_cursor_t &operator++();

  operator bool() const
  {
    return _block_id != BAD_ID;
  }

  int line() const { return _line; }
  int block_id() const { return _block_id; }
  int id() const { return _id; }
};

/* See superclass. This is syntactic sugar for the first format.
 */
class query_by_movie_cursor_t : public query_cursor_t
{
public:
  query_by_movie_cursor_t(std::istream &is) : query_cursor_t(is) { }
  int movie_id() const { return this->block_id(); }
  int user_id() const { return this->id(); }
};

/* See superclass. This is syntactic sugar for the second format.
 */
class query_by_user_cursor_t : public query_cursor_t
{
public:
  query_by_user_cursor_t(std::istream &is) : query_cursor_t(is) { }
  int movie_id() const { return this->id(); }
  int user_id() const { return this->block_id(); }
};

#define RATING_BLOCK_MARKER FLT_MAX // see read_ratings_blocks

/* Read ratings (or residuals) into a compact blocked array of structs. The 
 * structs do double duty. When the rating is RATING_BLOCK_MARKER, the id is a 
 * block id. When the rating is not RATING_BLOCK_MARKER, the id is an item id.
 * This can be used to read in user- or movie-blocked data files, like:
 *
 * movie_id:                    -- start of a movie "block"
 * user_id,rating[,...]
 * user_id,rating[,...]
 * ...
 * or:
 * user_id:                     -- start of user "block"
 * movie_id,rating[,...]
 * movie_id,rating[,...]
 * ...
 *
 * The last item in the list is a sentinel block marker with its id set to
 * BAD_ID. The return value is the number of structs put into the array r,
 * including the sentinel record.
 */
template <typename rating_t>
size_t read_ratings_blocks(id_rating_t<rating_t> *r, size_t r_len,
    std::istream &is)
{
  // Use a cursor to read the items in; we need the block structure, but the
  // block cursors would do lots of extra work.
  int last_block_id = BAD_ID;
  size_t n = 0;
  for (ratings_cursor_t<rating_t> rs(is); rs; ++rs) {
    assert(n < r_len);
    if (rs.block_id() != last_block_id) {
      r[n].id = rs.block_id();
      r[n].rating = RATING_BLOCK_MARKER;
      ++n;
      last_block_id = rs.block_id();
    }
    assert(n < r_len);
    r[n].id = rs.id();
    r[n].rating = rs.rating();
    ++n;

#ifndef NDEBUG
    // This can take a while; provide some tracing output.
    if (n % 5000000 == 0)
      TRACE<<"read "<<n<<" ratings and blocks"<<std::endl;
#endif
  }

  // Put in sentinel record.
  assert(n < r_len);
  r[n].id = BAD_ID;
  r[n].rating = RATING_BLOCK_MARKER;
  ++n;

  return n;
}

// For convenience.
template <typename rating_t>
bool is_block(id_rating_t<rating_t> *r, size_t i) {
  return r[i].rating == RATING_BLOCK_MARKER;
}

// For debugging. Movies must be ordered, and so must users.
template <typename rating_t>
void assert_r_ordered(id_rating_t<rating_t> *r, size_t n) {
#ifndef NDEBUG
  size_t i = 0;
  int last_movie_id = INT_MIN;
  do {
    assert(is_block(r, i));
    assert(last_movie_id < r[i].id);
    last_movie_id = r[i].id;

    int last_user_id = INT_MIN;
    ++i;
    while (!is_block(r, i)) {
      assert(last_user_id < r[i].id);
      last_user_id = r[i].id;
      ++i;
    }
  } while(r[i].id != BAD_ID);
#endif
}

/* Like ratings_block_cursor_t but works on an in-memory training set.
 * Example: see ratings_block_cursor_t
 */
template<typename rating_t>
class memory_ratings_block_cursor_t {
  id_rating_t<rating_t> *r;
protected:
  size_t n; // subclasses shouldn't change this
  size_t _begin;
  size_t _end;
  int _block_id;
public:
  memory_ratings_block_cursor_t(id_rating_t<rating_t> *r, size_t n)
    : r(r), n(n)
  {
    // List must now begin and end with movie.
    assert(is_block(r, 0) && is_block(r, n-1));

    this->home();
  }

  // Return to first record.
  void home() {
    _begin = 0;
    _end = 0;
    _block_id = BAD_ID;
    ++(*this);
  }

  memory_ratings_block_cursor_t<rating_t> &operator++()
  {
    // The end marker will end up on the sentinel at the end.
    if (_end >= n - 1) {
      ++_end;
      return *this;
    }

    assert(is_block(r, _end));
    _block_id = r[_end].id;

    // Scan for next block.
    _begin = _end + 1;
    do { ++_end; } while (!is_block(r, _end));

    assert(!is_block(r, _begin));
    assert(is_block(r, _end));

    return *(this);
  }

  operator bool() const {
    return _end < n;
  }

  const id_rating_t<rating_t> &operator [](size_t i) const {
    assert(*this); 
    assert(i < size());
    return r[_begin + i];
  }

  typedef id_rating_t<rating_t> * iterator;
  typedef const id_rating_t<rating_t> * const_iterator;

  iterator begin() { assert(*this); return &(r[_begin]); }
  iterator end() { assert(*this); return &(r[_end]); }
  const_iterator begin() const { assert(*this); return &(r[_begin]); }
  const_iterator end() const { assert(*this); return &(r[_end]); }
  size_t size() const { assert(*this); return this->_end - this->_begin; }
  int block_id() const { assert(*this); return _block_id; }
  int id(size_t j) const { return (*this)[j].id; }
  rating_t rating(size_t j) const { return (*this)[j].rating; }
};

/* See superclass. This is syntactic sugar for the first format.
 */
template<typename rating_t>
class memory_ratings_by_movie_block_cursor_t
  : public memory_ratings_block_cursor_t<rating_t>
{
public:
  memory_ratings_by_movie_block_cursor_t(
      id_rating_t<rating_t> *r, size_t n)
    : memory_ratings_block_cursor_t<rating_t>(r, n)
  { }
  int movie_id() const { return this->block_id(); }
  int user_id(size_t j) const { return this->id(j); }
};

/* See superclass. This is syntactic sugar for the second format.
 */
template<typename rating_t>
class memory_ratings_by_user_block_cursor_t
  : public memory_ratings_block_cursor_t<rating_t>
{
public:
  memory_ratings_by_user_block_cursor_t(
      id_rating_t<rating_t> *r, size_t n)
    : memory_ratings_block_cursor_t<rating_t>(r, n)
  { }
  int movie_id(size_t j) const { return this->id(j); }
  int user_id() const { return this->block_id(); }
};

/* Like ratings_block_cursor_t but works on an in-memory training set and
 * keeps an index so that it's easy to jump to particular block ids.
 * Example: see ratings_block_cursor_t
 */
template<typename rating_t>
class index_ratings_block_cursor_t
  : public memory_ratings_block_cursor_t<rating_t>
{
  typedef memory_ratings_block_cursor_t<rating_t> super_t;
  typedef std::map<int, std::pair<size_t, size_t> > index_t;
  index_t index;
public:
  index_ratings_block_cursor_t(id_rating_t<rating_t> *r, size_t n)
    : super_t(r, n)
  {
    // Build index and reset the cursor.
    for (; *this; ++(*this)) {
      index.insert(make_pair(super_t::_block_id,
        make_pair(super_t::_begin, super_t::_end)));
    }
    super_t::home();
  }

  // Jump to a block of ratings using the index.
  // If block_id invalid, invalidates the cursor (can still call home to reset).
  void jump(int block_id)
  {
    index_t::const_iterator it = this->index.find(block_id);
    if (it == this->index.end()) {
      super_t::_end = super_t::n + 1;
      return;
    }
    super_t::_block_id = block_id;
    super_t::_begin = it->second.first;
    super_t::_end = it->second.second;
  }
};

/* See superclass. This is syntactic sugar for the first format.
 */
template<typename rating_t>
class index_ratings_by_movie_block_cursor_t
  : public index_ratings_block_cursor_t<rating_t>
{
public:
  index_ratings_by_movie_block_cursor_t(
      id_rating_t<rating_t> *r, size_t n)
    : index_ratings_block_cursor_t<rating_t>(r, n)
  { }
  int movie_id() const { return this->block_id(); }
  int user_id(size_t j) const { return this->id(j); }
};

/* See superclass. This is syntactic sugar for the second format.
 */
template<typename rating_t>
class index_ratings_by_user_block_cursor_t
  : public index_ratings_block_cursor_t<rating_t>
{
public:
  index_ratings_by_user_block_cursor_t(
      id_rating_t<rating_t> *r, size_t n)
    : index_ratings_block_cursor_t<rating_t>(r, n)
  { }
  int movie_id(size_t j) const { return this->id(j); }
  int user_id() const { return this->block_id(); }
};

#endif // guard

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

